package practice.sort;

/**
 * 快速排序
 */
public class QuickSort extends SortAdaptor {

    public static void main(String[] args) {
        int[] nums = {3, 9, 10, 2, 3, 123, 239, 4, 13, 443, 23, 29, 3, 3, 3};
        quickSort(nums);
        for (int num :
                nums) {
            System.out.print(num + " ");
        }
    }

    public static void quickSort(int[] nums) {
        if (nums.length == 0) {
            return;
        }
        quickSort(nums, 0, nums.length - 1);
    }

    private static void quickSort(int[] nums, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }
        int partition = partition(nums, leftIndex, rightIndex);
        quickSort(nums, leftIndex, partition - 1);
        quickSort(nums, partition + 1, rightIndex);

    }

    private static int partition(int[] a, int leftIndex, int rightIndex) {
        int i = leftIndex, j = rightIndex + 1;
        int pivot = a[i];
        while (true) {
            while (++i < rightIndex && a[i] < pivot) ;
            while (leftIndex < --j && a[j] > pivot) ;
            if (i >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, leftIndex, j);
        return j;
    }

}
